1. Field of the Invention
The present invention relates to a exponentiation calculation apparatus and exponentiation calculation method.
2. Description of the Related Art
Nowadays, an encryption protocol (e.g., an ID based cryptogram, or a short signature) utilizing effectiveness of pairing has been proposed. Pairing using an elliptic curve of a large embedded degree k is effective in terms of safety. For example, a constitution method for an elliptic curve of k=2×r (r is an odd prime) has been proposed (see D. Freeman, M. Scott, E. Teske, “A taxonomy of pairing-friendly elliptic curves”, IACR ePrint Archive 2006/372) (reference [1]).
Several algorithms of pairing have been known. For example, Tate pairing over a finite field is such mapping as represented by Expression (1).<P,Q>m:E(Fq)[m]×E(Fq^k)/mE(Fq^k)→F*q^k/(F*q^k)m  (1)
Here, q is a power of a prime p, Fq is a finite field with q elements, and E(Fq) is an elliptic curve defined over the finite field Fq. m is coprime to q and it is a positive integer satisfying m|#E(Fq). The symbol ^ represents exponentiation operation. For example, q^k represents the kth power of q. An embedded degree k is a minimum positive integer satisfying m|(q^k−1). #E represents the number of points of the elliptic curve E (an order of a curve). a|b represents that a is divisor of b.
Tate pairing over the finite field is mapping of inputting an Fq rational point P on an elliptic curve E (Fq) and an Fq^k rational point Q on an elliptic curve E(Fq^k) and outputting an element on Fq^k.
In general, a procedure of a pairing calculation consists of the following two steps.
[First Stage] a Calculation of Pairing Including ambiguity (e.g., a Miller algorithm)
[Second Stage] Removal of Ambiguity
A value obtained on the first stage is an element of the finite field Fq^k. Since this value is representation including ambiguity, it is not suitable for use in an encryption protocol. Thus, on the second stage, ambiguity is removed from the value obtained on the first stage.
The calculation on the first stage will be referred to as a “pairing intermediate value calculation” and a value obtained by the pairing intermediate value calculation will be referred to as a pairing intermediate value. Further, the calculation on the second stage will be referred to as “final exponentiation”. A value obtained by the final exponentiation is a “pairing value” to be acquired.
To increase a speed of the pairing calculation, speeds of both the pairing intermediate value calculation and the final exponentiation must be increased. The speed of the pairing intermediate value calculation has been greatly increased. As to the final exponentiation, a speed-up technique when, e.g., r=3 (k=6) has been proposed (see Masaaki Shirase and Tsuyoshi Takagi and Eiji Okamoto, “Some Efficient Algorithms for the Final Exponentiation of ηT Pairing”, IACR ePrint Archive 2006/431)(reference [2]). However, the speed-up technique of the final exponentiation is not known.
Here, the final exponentiation is an operation of raising a pairing intermediate value represented by an element of the finite field Fq^k to the (q^k−1)/mth power in such a manner that the pairing intermediate value becomes unique as an element in a cyclic group of an order m.
For example, in reference [2], the following procedure of the final exponentiation is explained. That is, when r=3, the cyclic group of the order m is a partial group of a torus T6(Fq). Thus, the pairing value is raised to the (q^3−1)(q+1)th power in such a manner that the pairing value becomes unique as an element of the torus T6(Fq), and a result is further raised to the (q^2−q+1)/mth power.
Here, in the above-explained procedure, a calculation result becomes unique representation of a torus T2(Fq^3) when the pairing value is raised to the (q^3−1)th power. Therefore, utilizing a property that the calculation result is an element of the torus T2(Fq^3) to calculate the remaining (q+1)th power enables increasing the speed. Specifically, the number of times of multiplications in the (q+1)th power calculation can be reduced by using three relational expressions present in a set of input six numbers to replace given multiplications in the calculation by other multiplications.
A strategy for a reduction in the number of times of multiplications is not clear in reference [2]. However, according to reference [2], the number of times of multiplications in the (q+1)th power calculation can be reduced to nine times from 18 times (i.e., a double speed can be achieved in the (q+1)th power calculation).
As the technique of increasing the speed of the final exponentiation in the pairing calculation, the technique when r=3 (k=6) alone is conventionally known.